#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 090. 子集 II.py
@time: 2022/1/21 12:52
@desc: https://leetcode-cn.com/problems/subsets-ii/submissions/
> 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

@解题思路：
    1. 回溯
    2. 重复元素就先排序
    3. Ot(n*2^n), Os(n)
'''
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        # 因为有重复的元素，所以先排序
        nums.sort()
        def backtrack(start, path):
            res.append(path)
            for i in range(start, n):
                # 剪枝， num[i]已经固定过了，就可以跳过
                if i>start and nums[i]==nums[i-1]: continue
                backtrack(i+1, path + [nums[i]])

        res = []
        backtrack(0, [])
        return res